Euler 関数
a.k.a.
$ \varphi(n) は$ [1, n] の範囲の$ nと互いに素な自然数の個数を返す関数 $ \varphi(n)=n\prod_{p|n}\left(1-\frac1p\right)
導出
1. $ [1,p^{e_p}] の範囲の$ p^{e_p}と互いに素な自然数は$ p^{e_p}\left(1-\frac1p\right)個 $ p^{e_p}\left(1-\frac1p\right)=p^{e_p}-p^{e_p-1}
$ [1,p^{e_p}] の範囲の$ pの倍数は$ p^{e_p-1}個のため
$ 1p,2p,3p,\cdots,p^{e_p-1}pの$ p^{e_p-1}個ある
2. $ \varphi(n)=n\prod_{p|n}\left(1-\frac1p\right)
$ n\prod_{p|n}\left(1-\frac1p\right)=\prod_{p|n}p^{e_p}\left(1-\frac1p\right)
$ n=\prod_{p|n}p^{e_p}
$ \begin{cases}c\overset m\equiv a\\c\overset n\equiv b\end{cases}を満たす$ (a,b)\in(\Z/m\Z,\Z,n\Z)と$ c\in(\Z/m\,n\,\Z)を結ぶ全単射が存在
$ \gcd(m,a)=1,$ \gcd(n,b)=1とすると
$ \begin{cases}c\overset m\equiv a\\c\overset n\equiv b\end{cases}を満たす$ (a,b)と$ c\quad(\gcd(c,mn)=1)を結ぶ全単射が存在
1 対 1 対応なので$ cの個数は$ \varphi(mn)=\varphi(m)\varphi(n)
$ \gcd(m,a)=1を満たす$ aが$ \varphi(m)個存在
$ \gcd(n,b)=1を満たす$ bが$ \varphi(n)個存在
$ \gcd(mn,c)=1を満たす$ cが$ \varphi(mn)個存在
これらは$ (a,b)\leftrightarrow cの対応を付けられるので$ \varphi(m)\varphi(n)個存在
$ \therefore\varphi(mn)=\varphi(m)\varphi(n)